package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class combinationSum_ {
  LinkedList<Integer> list = new LinkedList<>();
  List<List<Integer>> result = new ArrayList<>();
  @Test
  public void combinationSumTest(){
    int[] nums = new int[]{2,3,5};
    int target = 8;
    backTracking(nums,target,0);
    System.out.println(result);
  }


  public void backTracking(int[] candidates, int target,int index) {
    Arrays.sort(candidates);
    if (candidates[0] > target){
      return;
    }
        if (Sum(list) == target){
          result.add(new LinkedList<>(list)); // new LinkedList<>(list)表示创建一个值和list一样的LinkedList对象
          return;
        }

        if (Sum(list) + candidates[0] > target){
          return;
        }
        /*加上这个index来控制元素选择就可以实现去重*/
        /*可以这样理解, 排序之后 选2 之后还可以选 35
        * 但选3 之后不用再选2了, 因为要是再选2的话 得到的结果集和
        * 一开始选2得到的结果集一样*/
        for (int i = index ; i < candidates.length ; i++){

          if (Sum(list) + candidates[i] > target){
            break;
          }
          list.add(candidates[i]);
          backTracking(candidates,target,i);
          list.removeLast();
        }
  }
  public static int Sum(LinkedList<Integer> list ){
    int sum = 0;
    for (Integer number : list) {
      sum += number;
    }
    return sum;
  }
}

